package com.lordjoe.sudoku;

import java.util.*;

/**
 * com.lordjoe.sudoku.SudokuConstraint
 * constraint - all known values of cells associated with constraints must be distinct
 * constraints are of tyoe row, column and box
 * User: Steve
 * Date: 4/7/12
 */
public class SudokuConstraint {
    public static final SudokuConstraint[] EMPTY_ARRAY = {};


    private final ConstraintType m_Type;
    private final int m_Index;
    private final SudokuCell[] m_Cells = new SudokuCell[SudokuBoard.getBoardSize()];
    private int m_MessageIndex;
    private final CellMessage[] m_CellMessages = new CellMessage[SudokuBoard.getBoardSize()];

    public SudokuConstraint(final ConstraintType pType, int index, SudokuBoard board) {
        m_Type = pType;
        m_Index = index;
        fillWithCells(pType, index, board);
    }

    /**
     * ****************************************************
     * This section is bookkeeping                        *
     * *****************************************************
     */

    public int getIndex() {
        return m_Index;
    }

    public String toString() {
        String name = getType().toString() + ":" + (getIndex() + 1);
        return name;
    }

    /**
     * reset for a new round of messaging
     */
    public void resetMessaging() {
        //  Arrays.fill(m_CellMessages, null);
        m_MessageIndex = 0;
    }

    /**
     * initialization code for a constraint
     *
     * @param pType !null type
     * @param index 0.. Boardsize usually 9
     * @param board !null board
     */
    protected void fillWithCells(final ConstraintType pType, final int index, final SudokuBoard board) {
        switch (pType) {
            case Row:
                fillWithRowCells(index, board);
                break;
            case Column:
                fillWithColumnCells(index, board);
                break;
            case Box:
                fillWithBoxCells(index, board);
                break;
        }
    }

    /**
     * @param row   row 0..9 in clasic sudoku
     * @param board !null board
     */
    private void fillWithRowCells(final int row, final SudokuBoard pBoard) {
        for (int col = 0; col < SudokuBoard.getBoardSize(); col++) {
            SudokuCell cell = pBoard.getCell(row, col);
            m_Cells[col] = cell;
            cell.addConstraint(this);
        }
    }

    /**
     * @param col   row 0..9 in clasic sudoku
     * @param board !null board
     */
    private void fillWithColumnCells(final int col, final SudokuBoard pBoard) {
        for (int row = 0; row < SudokuBoard.getBoardSize(); row++) {
            SudokuCell cell = pBoard.getCell(row, col);
            m_Cells[row] = cell;
            cell.addConstraint(this);
        }
    }

    /**
     * @param box   row 0..9 in clasic sudoku
     * @param board !null board
     */
    private void fillWithBoxCells(final int box, final SudokuBoard pBoard) {
        for (int index = 0; index < SudokuBoard.getBoardSize(); index++) {
            SudokuCell cell = pBoard.getCellFromBox(box, index);
            // System.out.print(" " + cell);
            m_Cells[index] = cell;
            cell.addConstraint(this);
        }
        System.out.println();
    }

    /**
     * row, col or box
     *
     * @return !null type
     */
    public ConstraintType getType() {
        return m_Type;
    }

    /**
     * true if all cells satisfy the constraint
     *
     * @return
     */
    public boolean isSatisfied() {
        boolean[] filled = new boolean[SudokuBoard.getBoardSize()];
        for (SudokuCell cell : m_Cells) {
            Integer value = cell.getValue();
            if (value != null) {
                int index = value - 1;
                if (filled[index])
                    return false; // some other cell has the value
                filled[index] = true; //this value used
            }
        }
        return true; // no violationss
    }

    /**
     * remove from phi array any specified values
     * only called on initialization
     *
     * @param phi array of priors
     */
    public void removeDeterminedStates(final double[] phi) {
        for (SudokuCell cell : m_Cells) {
            if (cell.hasValue()) {
                int index = cell.getValue() - 1;
                phi[index] = 0;
            }
        }
    }

    protected void addCellMessage(CellMessage cm) {
        m_CellMessages[m_MessageIndex++] = cm;
    }


    /*******************************************************
     *  This section is the algorithm                        *
     *******************************************************/


    /**
     * stop on interesting cases - for debugging
     */
    private void breakIfInteresting() {
        int col = getIndex();
        if (getType() == ConstraintType.Box && col == 0)
            SudokuBoard.breakHere();
    }

    /**
     * constraint are distinct.
     * Belief propagation operates by sending probabilistic
     * messages between adjacent nodes in the graph. The
     * message that constraint node Cm sends to cell Sn is
     * rmn(x) = P(Cm is satisedjSn = x) = P(CmjSn = x)
     * that is, the probability that constraint Cm is satised
     * when the cell Sn contains x (see [11] for related discus-
     * sion for LDPC decoding). The ?message? from Cm to
     * Sn is actually a probability vector, e.g.,
     * rmn =
     * <p/>
     * rmn(1); rmn(2); : : : ; rmn(9)
     */
    public void messageCells() {
        breakIfInteresting();
        Set<Integer> myLegalValues = getMyLegalValues();

        Integer[] integers = myLegalValues.toArray(new Integer[0]);
        Arrays.sort(integers);
        for (SudokuCell cell : m_Cells) {
            if (cell.hasValue())
                continue; // do not reset cells
            ConstraintMessage msg = buildCellMessage(cell, integers);
            cell.addConstraintMessage(msg);
        }
    }

    private Set<Integer> getMyLegalValues() {
        int yech = 0;
        if(getType() == ConstraintType.Row && getIndex() == 3)
            yech = 0; // break here

        Set<Integer> myLegalValues = new HashSet<Integer>();
        // get all values
        for (int i = 0; i < SudokuBoard.getBoardSize(); i++) {
            myLegalValues.add(i + 1);
        }
        // remove all
        for (SudokuCell cell : m_Cells) {
            if (cell.hasValue())
                myLegalValues.remove(cell.getValue()); // do not reset cells
        }
        return myLegalValues;
    }


    /**
     * here we build a message back to the cells - this step is the
     * critical part of the algorithm - everything else is bookkeeping
     * This is my attempt at the Sum Product
     *
     * @param cell
     * @return
     */
    protected ConstraintMessage buildCellMessage(SudokuCell cell, Integer[] legalValues) {
        ConstraintMessage msg = new ConstraintMessage(this, cell);
        double[] probabilityForCell = msg.getValues();
        // if only 1 legal value we are tone
        if (legalValues.length == 1) {
            probabilityForCell[legalValues[0] - 1] = 1;
            return msg;
        }
        Integer[] iters = Arrays.copyOf(legalValues, legalValues.length);
        // set legal values to 1 others to 0
//        for (int i = 0; i < iters.length; i++) {
//            probabilityForCell[iters[i] - 1] = 1;
//        }

        double[][] cellphis = new double[legalValues.length - 1][];
        int freeIndex = 0;
        // gather phi (probability from cells which are not this and have values
        for (int index = 0; index < m_CellMessages.length; index++) {
            CellMessage other = m_CellMessages[index];
            SudokuCell cell1 = other.getCell();
            if (cell1 == cell || cell1.hasValue())
                continue;
            double[] phi = other.getValues();
            cellphis[freeIndex++] = phi;
        }
        // now for every permutation
        do {
            freeIndex = 0;
            // first value is assigned to this cell
            int valueOfCell = iters[0] - 1;
            double product = 1;
            // for all other cells
            for (int index = 0; index < cellphis.length; index++) {
                // get probability each item
                double[] phi = cellphis[index];
                // get value of premutation - + 1 sincel 0th entry is for the cell
                // -1 because we use 1..9 not 0..8
                int valueCellThisPermutation = iters[index + 1] - 1;
                product *= phi[valueCellThisPermutation];
                if(product == 0)
                    break;
            }
            if(product == 0)
                  continue;
             probabilityForCell[valueOfCell] += product;
        } while (Permutations.permuteLexically(iters));


        msg.normalize();
        return msg;
    }


    /**
     * here we build a message back to the cells - this step is the
     * critical part of the algorithm - everything else is bookkeeping
     * This is the original and probably wrong code
     *
     * @param cell
     * @return
     */
    protected ConstraintMessage buildCellMessageOld(SudokuCell cell, Integer[] legalValues) {
        Integer[] iters = Arrays.copyOf(legalValues, legalValues.length);
        ConstraintMessage msg = new ConstraintMessage(this, cell);
        double[] ret = msg.getValues();
        // set legal values to 1 others to 0
        for (int index = 0; index < m_CellMessages.length; index++) {
            CellMessage other = m_CellMessages[index];

            SudokuCell cell1 = other.getCell();
            if (cell1 == cell)
                continue;
            double[] phi = other.getValues();
            for (int i = 0; i < phi.length; i++) {
                ret[i] *= 1 - phi[i];
            }
        }


        msg.normalize();
        return msg;
    }


}
